/*
 * Совпадающие строки
 */

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif
#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))
#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))
#define MIN(a, b)	((a) < (b) ? (a) : (b))

struct trie_node {
	/* struct trie_node *leaf['z' - 'a' + 1]; */
	struct st_node *set;
	int freq;
};

/* search tree node */
struct st_node {
	char key;
	struct trie_node *ptr;
	struct st_node *left, *right;
};

/* {{{ memory allocation wrappers */
extern char *
s_calloc(size_t n, size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): calloc %lu times %lu bytes (tot %.4f MiB)\n",
			__func__, n, size, ((float) n * size) / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = calloc(n, size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern char *
s_malloc(size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): malloc %lu bytes (%.4f MiB)\n",
			__func__, size, (float) size / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = malloc(size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern char *
s_realloc(char *oldptr, size_t newsize)
{
	void *newptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): realloc oldptr %p for new size of %lu (%.4f MiB)\n",
			__func__, oldptr, newsize, (float) newsize / (1024.0f * 1024.0f));
#endif
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): newptr %p\n", __func__, newptr);
#endif /* MEMDEBUG */
	return newptr;
}
/* }}} */

/* simple search-tree-based set */
struct st_node *
set_add(struct st_node *root, char new_key)
{
	struct st_node *prev;

	if (root == NULL)
		return NULL; /* look out for this too */

	while (root) {
		prev = root;
		if (new_key > root->key)
			root = root->right;
		else
			root = root->left;
	}
	if (new_key > prev->key)
		root = prev->right = s_calloc(1UL, sizeof *prev);
	else
		root = prev->left = s_calloc(1UL, sizeof *prev);
	root->key = new_key;
	root->ptr = root->left = root->right = NULL;
	return root;
}

struct st_node *
set_seek(struct st_node *root, char key)
{
	while (root) {
		if (root->key == key)
			return root;
		else if (root->key > key)
			root = root->left;
		else
			root = root->right;
	}

	return NULL; /* ouch! ya gotta look out for that! */
}

/* trie */
int
trie__reg_word(struct trie_node *root, const char *w)
{
	register int i;
	struct st_node *next;

	i = 0;
	while (w[i]) {
		/*
		 * if (root->leaf[w[i] - 'a'] == NULL)
		 *     root->leaf[w[i] - 'a'] = s_calloc(1UL, sizeof *root);
		 * root = root->leaf[w[i++] - 'a'];
		 */
		if (root->set == NULL) {
			root->set = s_calloc(1UL, sizeof *root->set);
			root->set->key = w[i];
			root->set->ptr = s_calloc(1UL, sizeof *root);
		}

		if (next = set_seek(root->set, w[i]), next == NULL) {
			next = set_add(root->set, w[i]);
			next->ptr = s_calloc(1UL, sizeof *root);
		}
		root = next->ptr;
		i++;
	}
	if (!w[i])
		root->freq++;

	return root->freq - 1;
}

void
print_set(struct st_node *st)
{
	if (st->left)
		print_set(st->left);
	fputc(st->key, stderr);
	if (st->right)
		print_set(st->right);
}

void
traveller(struct trie_node *node, struct st_node *link)
{
	if (node && !link) {
		if (node->set) {
			#ifdef DEBUG
			fprintf(stderr, "%lx: node->set ~= <", &node);
			print_set(node->set);
			fprintf(stderr, ">\n");
			#endif /* DEBUG */

			traveller(NULL, node->set);
		}
		free(node);
	} else if (!node && link) {
		S_assert(link->ptr);

		if (link->left)
			traveller(NULL, link->left);
		if (link->right)
			traveller(NULL, link->right);
		traveller(link->ptr, NULL);
		free(link);
	} else {
		fprintf(stderr, "ergh?\n");
	}
}

int
main(int argc, char **argv)
{
	char *word, *lf;
	struct trie_node *trie;

	word = s_malloc(500002UL);
	trie = s_calloc(1UL, sizeof *trie);

	while (fgets(word, 500001, stdin)) {
		if (lf = strrchr(word, '\n'), lf)
			*lf = '\0';
		printf("%d\n", trie__reg_word(trie, word));
	}

	traveller(trie, NULL);
	free(word);
	return 0;
}
